package 回溯算法;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-24 23:21
 **/
public class N皇后 {
    List<List<String>> res = new LinkedList<>();


    public List<List<String>> solveNQueens(int n) {
        //初始化棋盘 '.'表示空 'Q'表示皇后位置
        List<String> board = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append('.');
            }
            board.add(sb.toString());
        }
        backtrace(board, 0);
        return res;


    }

    //路径:board中小于row的行中放了的皇后的位置
    //选择列表:第row行所有的列都是皇后放置的位置
    //结束条件:row超过board的最后一行
    public void backtrace(List<String> board, int row) {
        //触发结束条件
        if (row == board.size()) {
            res.add(new LinkedList<String>(board));
            return;
        }
        String oldRow = board.get(row);
        StringBuilder sb = new StringBuilder(oldRow);
        int n = oldRow.length();
        for (int col = 0; col < n; col++) {
            //排除不合法条件
            if (!isValid(board, row, col)) {
                continue;
            }
            //做选择
            sb.setCharAt(col, 'Q');
            //更新board
            board.set(row, new String(sb));
            //进入下一层
            backtrace(board, row + 1);
            //撤销选择
            sb.setCharAt(col, '.');
            board.set(row, new String(sb));

        }

    }

    public boolean isValid(List<String> board, int row, int col) {
        int n = board.get(0).length();
        //检查列是否有皇后冲突
        //前row行的第col列为'Q' 则有冲突 返回false

        for (int i = 0; i < row; i++) {
            if (board.get(i).charAt(col) == 'Q') {
                return false;
            }
        }
        //检查对角线是否有皇后冲突
        //col1-col2==row1-row2
        for (int i = 0; i < row; i++) {
            //第i行皇后的下标为j
            String curStr = board.get(i);
            int j = curStr.indexOf('Q');
            //绝对值

            if (Math.abs(row - i) == Math.abs(col - j))
                return false;
        }
        return true;


    }

    public static void main(String[] args) {
        N皇后 t = new N皇后();
        t.solveNQueens(5);
        System.out.println(t.res);

    }


}
